/*
 *  Arrow
 *
 *  Created by David Giovannini on 1/5/07.
 *  Copyright 2007 Software by Jove. All rights reserved.
 *
 */
 
#include <algorithm>

namespace SBJ
{

template < typename T >
NodeQueue< T >::NodeQueue( void )
: m_size( 0 )
, m_achievedSize( 0 )
{
	m_head.m_next = &m_tail;
	m_head.m_queue = this;
	m_tail.m_prev = &m_head;
	m_tail.m_queue = this;
}

template < typename T >
NodeQueue< T >::~NodeQueue( void )
{
	clear();
}

template < typename T >
void
NodeQueue< T >::clear( void )
{
	m_size = 0;
	Node* node = m_tail.prev();
	while ( node != &m_head )
	{
		Node* prev = node->prev();
		delete node;
		node = prev;
	}
	m_head.m_next = &m_tail;
	m_tail.m_prev = &m_head;
}

template < typename T >
void
NodeQueue< T >::push_front( T* node )
{
	push_after( &m_head, node );
}

template < typename T >
void
NodeQueue< T >::push_back( T* node )
{
	push_before( &m_tail, node );
}

template < typename T >
T*
NodeQueue< T >::pop_back( void )
{
	T* node = back();
	if ( node ) pop( node );
	return node;
}

template < typename T >
T*
NodeQueue< T >::pop_front( void )
{
	T* node = front();
	if ( node ) pop( node );
	return node;
}

template < typename T >
T*
NodeQueue< T >::front( void )
{
	return ( empty() ? static_cast< T* >( 0 ) : static_cast< T* >( m_head.next() ) );
}

template < typename T >
T*
NodeQueue< T >::back( void )
{
	return ( empty() ? static_cast< T* >( 0 ) : static_cast< T* >( m_tail.prev() ) );
}

template < typename T >
const T*
NodeQueue< T >::front( void ) const
{
	return ( empty() ? static_cast< T* >( 0 ) : static_cast< T* >( m_head.next() ) );
}

template < typename T >
const T*
NodeQueue< T >::back( void ) const
{
	return ( empty() ? static_cast< T* >( 0 ) : static_cast< T* >( m_tail.prev() ) );
}

template < typename T >
size_t
NodeQueue< T >::size( void ) const
{
	return m_size;
}

template < typename T >
bool
NodeQueue< T >::empty( void ) const
{
	return ( m_size == 0 );
}

template < typename T >
typename NodeQueue< T >::Node*
NodeQueue< T >::pop( Node* node )
{
	--m_size;
	Node* slot = ( node->m_next ? node->m_next : node->m_prev );
	if ( node->m_prev ) node->m_prev->m_next = node->m_next;
	if ( node->m_next ) node->m_next->m_prev = node->m_prev;
	node->m_next = 0;
	node->m_prev = 0;
	node->m_queue = 0;
	return slot;
}

template < typename T >
void
NodeQueue< T >::push_after( Node* where, Node* node )
{
	if ( node->m_queue ) node->m_queue->pop( node );
	++m_size;
	m_achievedSize = std::max( m_achievedSize, m_size );
	if ( where->m_next ) where->m_next->m_prev = node;
	node->m_next = where->m_next;
	where->m_next = node;
	node->m_prev = where;
	node->m_queue = this;
}

template < typename T >
void
NodeQueue< T >::push_before( Node* where, Node* node )
{
	if ( node->m_queue ) node->m_queue->pop( node );
	++m_size;
	m_achievedSize = std::max( m_achievedSize, m_size );
	if ( where->m_prev ) where->m_prev->m_next = node;
	node->m_prev = where->m_prev;
	where->m_prev = node;
	node->m_next = where;
	node->m_queue = this;
}
}